package com.uu.study;

import org.junit.Test;

import java.util.Objects;

/**
 * @desc 二叉树遍历
 * @author liuph
 * @date 2022/02/22 17:03
 */
public class TreeTraverse {


    /**
     *
     * <pre>
     * 创建一个二叉树，形式；
     *
     *
     *        1
     *       / \
     *      2   3
     *     / \   \
     *    4   5   6
     *  </pre>
     */
    public TreeNode createTree(){
        TreeNode treeNode4 = new TreeNode(4, null, null);
        TreeNode treeNode5 = new TreeNode(5, null, null);
        TreeNode treeNode6 = new TreeNode(6, null, null);


        TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);
        TreeNode treeNode3 = new TreeNode(3, null, treeNode6);
        return new TreeNode(1, treeNode2, treeNode3);
    }

    public void firstTraverse(TreeNode node){
        System.out.println("当前遍历节点：" + node.getData());

        TreeNode leftNode = node.getLeftNode();
        TreeNode rightNode = node.getRightNode();

        if(Objects.nonNull(leftNode)){
            firstTraverse(leftNode);
        }
        if(Objects.nonNull(rightNode)){
            firstTraverse(rightNode);
        }
    }

    public void middleTraverse(TreeNode node){
        TreeNode leftNode = node.getLeftNode();
        TreeNode rightNode = node.getRightNode();

        if(Objects.nonNull(leftNode)){
            middleTraverse(leftNode);
        }
        System.out.println("当前遍历节点：" + node.getData());

        if(Objects.nonNull(rightNode)){
            middleTraverse(rightNode);
        }
    }

    public void backTraverse(TreeNode node){
        TreeNode leftNode = node.getLeftNode();
        TreeNode rightNode = node.getRightNode();

        if(Objects.nonNull(leftNode)){
            backTraverse(leftNode);
        }
        if(Objects.nonNull(rightNode)){
            backTraverse(rightNode);
        }
        System.out.println("当前遍历节点：" + node.getData());
    }

    @Test
    public void traverseTest(){
        System.out.println("----------前序遍历----------");
        TreeNode tree = createTree();
        firstTraverse(tree);

        System.out.println("----------中序遍历----------");
        middleTraverse(tree);

        System.out.println("----------后序遍历----------");
        backTraverse(tree);
    }

}
